package com.it.data_linkedList.leetcode;

import java.util.Objects;

/**
 * @Author: Coke
 * @DateTime: 2023/06/06/22:01
 * @注释: 删除有序链表重复节点
 **/
public class E04LeetCode83 {
    
    /**
     * @param node: 有序链表（有重复节点）
     * @return ListNode
     * @作者: Coke
     * @注释: 方法一（重复元素保留一个）
     * @DateTime: 2023/6/6 22:13
     */
    public static ListNode deleteRepetition (ListNode node) {
        // 如果 链表为空 或者 只有一个节点 直接俄返回
        if (node == null || node.next == null) {
            return node;
        }
        ListNode s = new ListNode(- 1, node); // 哨兵
        ListNode n1 = s.next;
        ListNode n2 = n1.next;
        if (Objects.equals(n1.val, n2.val)) {
            ListNode x = n2;
            while (x.next != null && Objects.equals(n1.val, x.next.val)) {
                x = x.next;
            }
            return deleteRepetition(x);
        } else {
            n1.next = deleteRepetition(n2);
            return n1;
        }
    }
    
    /**
     * @param node: 有序链表（有重复节点）
     * @return ListNode
     * @作者: Coke
     * @注释: 方法二（重复元素全部删除）
     * @DateTime: 2023/6/6 22:13
     */
    public static ListNode deleteRepetition2 (ListNode node) {
        // 如果 链表为空 或者 只有一个节点 直接俄返回
        if (node == null || node.next == null) {
            return node;
        }
        if (node.val == node.next.val) {
            ListNode x = node.next.next;
            while (x != null && node.val == x.val) {
                x = x.next;
            }
            return deleteRepetition2(x);
        } else {
            node.next = deleteRepetition2(node.next);
            return node;
        }
    }
}